package com.faiz.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        // 滑动窗口，动态统计窗口中的词频
        List<Integer> res = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        if (sLen >= pLen) {
            char[] sChars = s.toCharArray();
            char[] pChars = p.toCharArray();
            // 记录p的词频
            int[] pCounts = new int[26];
            // 记录窗口中的词频
            int[] sCounts = new int[26];
            // 窗口的右端和左端
            int i = 0;
            for (; i < pLen; i++) {
                pCounts[pChars[i] - 'a']++;
                sCounts[sChars[i] - 'a']++;
            }
            if (Arrays.equals(sCounts, pCounts)) res.add(0);
            for (; i < sLen; i++) {
                sCounts[sChars[i] - 'a']++;
                sCounts[sChars[i - pLen] - 'a']--;
                if (Arrays.equals(sCounts, pCounts)) res.add(i - pLen + 1);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        FindAnagrams findAnagrams = new FindAnagrams();
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams.findAnagrams(s, p));
    }
}
